// https://leetcode.cn/problems/binary-search/description/
// https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
// 二分查找的前提是有序数组 如果无须需要先使用sort方法排序一下

const binarySearch = (arr, target) => {
  if (!Array.isArray(arr) || !arr.length) return;
  let left = 0,
    right = arr.length - 1;
  while (left <= right) {
    // 不直接使用 (left+right)/2 是为了防止左右相加大于js数字限制
    // 最好使用 left + Math.floor((right - left) / 2)
    // 这里使用位运算 直接保留的是整数位 小数位舍弃

    // let mid = Math.floor((right + left) / 2) 这样有超出数字范围的危险
    // let mid = left + ((right - left) >> 1);
    let mid = left + Math.floor((right - left) / 2);
    if (arr[mid] > target) {
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      return mid;
    }
  }
  return -1;
};

const arr = [1, 2, 3, 4, 5, 6];
console.log(binarySearch(arr, 66));


